package contest.sweek203;

import java.util.TreeMap;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/8/24 17:56
 */
public class Solution3 {

    public int findLatestStep(int[] arr, int m) {
        TreeMap<Integer,Integer> map = new TreeMap<>();
        int n = arr.length;
        map.put(1, n);
        if (m == n) return n;
        for (int i = n - 1; i >= 0; i--) {
            int idx = arr[i];
            int start = map.floorKey(idx);
            int end = map.get(start);
            if (idx > start) {
                if (idx - start == m) return i;
                map.put(start, idx-1);
            }
            if (idx < end) {
                if (end - idx == m) return i;
                map.put(idx+1, end);
            }
        }
        return -1;
    }

}
